enum Color { RED, BLACK };

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Color _col;

    RBTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
    {}
};

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    bool insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
                return false;
        }

        cur = new Node(kv);
        cur->_col = RED;
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else
            parent->_left = cur;
        cur->_parent = parent;

        while (parent && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            assert(grandfather && grandfather->_col == BLACK);

            if (grandfather->_left == parent)
            {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (parent->_left == cur)
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if (parent->_right == cur)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }

        _root->_col = BLACK;
        return true;
    }

    //Node* find(const K& k)
    //{
    //    Node* cur = _root;
    //    while (cur)
    //    {
    //        if (cur->_kv.first < k)
    //            cur = cur->_right;
    //        else if (cur->_kv.first > k)
    //            cur = cur->_left;
    //        else 
    //            return cur;
    //    }
    //    return nullptr;
    //}

    ~RBTree() { _destroy(_root); _root = nullptr; }
    void InOrder() { _InOrder(_root); }

    bool isRBTree()
    {
        if (_root == nullptr)
            return true;

        if (_root->_col == RED)
            return false;

        int benchmake = 0;
        return _isRBTree(_root, 0, benchmake);
    }

private:

    void RotateR(Node* parent)
    {
        Node* sub = parent->_left;
        Node* subR = sub->_right;

        parent->_left = subR;
        if (subR)
            subR->_parent = parent;

        Node* ppNode = parent->_parent;
        sub->_right = parent;
        parent->_parent = sub;

        if (parent == _root)
        {
            _root = sub;
            sub->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = sub;
            else
                ppNode->_right = sub;
            sub->_parent = ppNode;
        }
    }

    void RotateL(Node* parent)
    {
        Node* sub = parent->_right;
        Node* subL = sub->_left;

        parent->_right = subL;
        if (subL)
            subL->_parent = parent;

        Node* ppNode = parent->_parent;
        sub->_left = parent;
        parent->_parent = sub;

        if (parent == _root)
        {
            _root = sub;
            sub->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = sub;
            else
                ppNode->_right = sub;
            sub->_parent = ppNode;
        }
    }

    bool _isRBTree(Node* root, int blacknum, int& benchmake)
    {
        if (root == nullptr)
        {
            if (benchmake == 0)
                benchmake = blacknum;

            if (blacknum != benchmake)
                return false;

            return true;
        }

        if (root->_col == BLACK)
            blacknum++;

        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "出现连续的红色节点~错误~" << endl;
            return false;
        }

        return _isRBTree(root->_left, blacknum, benchmake) && _isRBTree(root->_right, blacknum, benchmake);
    }

    void _destroy(Node* root)
    {
        if (root == nullptr)
            return;

        _destroy(root->_left);
        _destroy(root->_right);
        delete root;
    }

    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_kv.first << ':' << root->_kv.second << endl;
        _InOrder(root->_right);
    }

private:
    Node* _root = nullptr;
};

